package offer;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author Elephas
 * @Date 2022/2/10
 **/
@FunctionalInterface
public interface Merge {
    int[][] merge(int[][] intervals);
}
class HMNodeImpl1 implements Merge{
    static final int[][] TEST_01 = new int[][]{{2,3},{5,5},{2,2},{3,4},{3,4}};
    public static void main(String[] args) {
        new MergeImpl2().merge(TEST_01);
    }

    @Override
    public int[][] merge(int[][] intervals) {
        boolean stop = false;
        int currentSize = intervals.length;
        int n;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        while(!stop) {
            stop = true;
            n = currentSize;
            currentSize = 0;
            for (int i = 0; i < n - 1; i++) {
                int[] cur = intervals[i];
                int[] next = intervals[i + 1];
                int a = cur[0], b = cur[1], c = next[0], d = next[1];

            /*  假设 cur 左右两端为 a,b ; next 左右两端为 c,d.
                a c b d -> a d
                c a b d -> c d
                a c d b -> a b
                等位交换
                c d a b -> c b
                c a d b -> c b
                c a d b -> c d ; x
                a c d b -> a d ; x
             */
                if (b < c) {
                    intervals[currentSize++] = cur;
                } else if (d < a) {
                    intervals[currentSize++] = next;
                    intervals[i + 1] = cur;
                } else{
                    stop = false;
                    if (a <= c && c <= b && b <= d) {
                        next[0] = a;
                        next[1] = d;

                    } else if (a <= c && c <= d && d <= b) {
                        next[0] = a;
                        next[1] = b;
                    } else if (c <= a && a <= b && b <= d) {
                        next[0] = c;
                        next[1] = d;
                    } else if (c <= a && a <= d && d <= b) {
                        next[0] = c;
                        next[1] = b;
                    }
                }
            }
            intervals[currentSize++] = intervals[n - 1];
        }
        int[][] ans = new int[currentSize][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = intervals[i];
        }
        return ans;

    }
}

class MergeImpl2 implements Merge{

    @Override
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(x,y) -> x[0] - y[0]);
        int n = intervals.length;
        int currentSize = 0;
        for (int i = 0; i < n - 1; i++) {

            int[] cur = intervals[i];
            int[] next = intervals[i + 1];
            int a = cur[0], b = cur[1], c = next[0], d = next[1];

            if (b < c) {
                intervals[currentSize++] = cur;
            } else if (d < a) {
                intervals[currentSize++] = next;
                intervals[i + 1] = cur;
            } else if (a <= c && c <= b && b <= d) {
                next[0] = a;
                next[1] = d;

            } else if (a <= c && c <= d && d <= b) {
                next[0] = a;
                next[1] = b;
            } else if (c <= a && a <= b && b <= d) {
                next[0] = c;
                next[1] = d;
            } else if (c <= a && a <= d && d <= b) {
                next[0] = c;
                next[1] = b;
            }
        }
        intervals[currentSize++] = intervals[n - 1];
        int[][] ans = new int[currentSize][];
        for (int i = 0; i < currentSize; i++) {
            ans[i] = intervals[i];
        }
        return ans;
    }
}
class MergeImpl3 implements Merge{
    @Override
    public int[][] merge(int[][] intervals) {
        // sort then merge
        Arrays.sort(intervals, (i1, i2) -> (i1[0] - i2[0]));
        int len = intervals.length;
        int i = 1, left = 0;
        while(i < len){
            int[] interval = intervals[i];
            int[] leftMostInterval = intervals[left];
            int ls = leftMostInterval[0], le = leftMostInterval[1], rs = interval[0], re = interval[1];
            if(le < rs){
                // can not merge.
                left++;
                intervals[left] = interval;
            }else{
                // can merge.
                int l = Math.min(ls, rs);
                int r = Math.max(le, re);
                leftMostInterval[0] = l;
                leftMostInterval[1] = r;
            }
            i++;
        }
        int[][] newIntervals = new int[left + 1][];
        for(i = 0; i < left + 1; i++){
            newIntervals[i] = intervals[i];
        }
        return newIntervals;
    }
}